# 描述
# 假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
# 给定两个这种链表，请生成代表两个整数相加值的结果链表。
# 例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
# 示例1
# 输入：
# [9,3,7],[6,3]
# 复制
# 返回值：
# {1,0,0,0}

class Solution:
    def addInList(self , head1 , head2 ):
        # write code here
        list1=''
        list2=''
        while head1.next!=None and head2.next!=None:
            list1=list1+str(head1.val)
            list2=list2+str(head2.val)
            head1=head1.next
            head2=head2.next
        while head1:
            list1=list1+str(head1.val)
            head1=head1.next
        while head2:
            list2=list2+str(head2.val)
            head2=head2.next
        return str(int(list1)+int(list2))  
so=Solution()
result=so.addInList(node1, node2)
printlink(result)








##别人解法
class Solution:
    def addInList(self, head1, head2):
        # write code here
        if head1 == None:
            return head2
        if head2 == None:
            return head1
         
        '''存入栈'''
        s1, s2 = [], []
        while head1:
            s1.append(head1.val)
            head1 = head1.next
        while head2:
            s2.append(head2.val)
            head2 = head2.next
         
        '''每次从栈末尾取出一个数进行相加，记录进位值并更新输出结果'''
        i = 0  # 进位值
        temp = ListNode(0) # 链表尾部
        while len(s1)>0 and len(s2)>0:
            num1 = int(s1.pop())
            num2 = int(s2.pop())
            node = ListNode((num1 + num2 + i)%10) # 当前结果
            i = (num1 + num2 + i)//10 # 更新进位值
            node.next = temp.next # 头插法，将新生成的数插入到当前链表的头部
            temp.next = node
         
        '''处理其余特殊情况：s1先为空、s2先为空'''
        while len(s1)>0:
            num = int(s1.pop())
            node = ListNode((num + i)%10)
            i = (num + i)//10
            node.next = temp.next 
            temp.next = node
             
        while len(s2)>0:
            num = int(s2.pop())
            node = ListNode((num + i)%10)
            i = (num + i)//10
            node.next = temp.next
            temp.next = node
             
        return temp.next